package likou;

import java.util.*;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2021/12/06 08:19
 */
public class _5932 {
    public static void main(String[] args) {
        _5932 one = new _5932();
        one.validArrangement(new int[][]
                {{999, 990}, {356, 511}, {192, 879}, {246, 945}, {322, 602}, {776, 246}, {248, 126}, {503, 284}, {126, 164}, {494, 731}, {862, 382}, {731, 578}, {511, 277}, {122, 731}, {578, 99}, {731, 277}, {847, 538}, {246, 494}, {284, 138}, {382, 899}, {811, 439}, {164, 99}, {485, 307}, {618, 320}, {494, 511}, {413, 248}, {945, 356}, {990, 614}, {138, 18}, {164, 862}, {277, 164}, {826, 737}, {277, 322}, {618, 122}, {291, 639}, {288, 11}, {624, 485}, {740, 452}, {614, 740}, {307, 903}, {457, 412}, {538, 961}, {439, 122}, {961, 999}, {639, 822}, {903, 503}, {961, 776}, {138, 538}, {122, 826}, {99, 138}, {949, 175}, {452, 847}, {320, 624}, {879, 457}, {511, 961}, {835, 692}, {18, 949}, {737, 413}, {822, 999}, {11, 726}, {692, 618}, {899, 835}, {726, 192}, {999, 452}, {602, 811}, {452, 618}, {175, 246}, {99, 291}, {412, 494}}
        );
    }

    List<Integer> res;
    boolean p = false;// 结束标志

    public int[][] validArrangement(int[][] pairs) {
        Map<Integer, Deque<Integer>> map = new HashMap<>();
        Map<Integer, Integer> start_end = new HashMap<>();
        res = new ArrayList<>();
        for (int[] ints : pairs) {
            Deque<Integer> list = map.getOrDefault(ints[0], new LinkedList<>());
            list.offerLast(ints[1]);
            map.put(ints[0], list);
            start_end.merge(ints[0], 1, Integer::sum);
            start_end.merge(ints[1], -1, Integer::sum);
        }
        int start = pairs[0][0], end = pairs[0][1];
        for (Integer key : start_end.keySet()) {
            if (start_end.get(key) == 0) continue;
            if (start_end.get(key) == 1) start = key;
            if (start_end.get(key) == -1) end = key;
        }
        dfs(start, map);
        Collections.reverse(res);
        int[][] resa = new int[pairs.length][2];
        for (int i=0;i<res.size()-1;i++){
            resa[i] = new int[]{res.get(i),res.get(i+1)};
        }
        return resa;
    }

    public void dfs(int key, Map<Integer, Deque<Integer>> map) {
        Deque<Integer> deque = map.get(key);
        while (deque != null && !deque.isEmpty()) {
            int nowKey = deque.pollLast();
            dfs(nowKey, map);
        }
        res.add(key);
    }
}